package LeetCode;

public class LC_449_SerializeandDeserializeBST {

    public static void main(String[] args) {

    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static class Codec {

        public String serialize(TreeNode root) {
            StringBuilder sb = new StringBuilder();
            serializedfs(root, sb);
            return sb.toString();
        }

        private void serializedfs(TreeNode root, StringBuilder sb) {
            if (root == null) return;
            sb.append(root.val).append(" ");
            serializedfs(root.left, sb);
            serializedfs(root.right, sb);
        }

        public TreeNode deserialize(String data) {
            if (data.length() == 0) return null;
            String[] list = data.split(" ");
            TreeNode dummy = new TreeNode(0);
            deserializedfs(list, 0, dummy, true, Integer.MIN_VALUE, Integer.MAX_VALUE);
            return dummy.left;
        }

        private int deserializedfs(String[] list, int pos, TreeNode par, boolean isleft, int lower, int upper) {
            if (pos >= list.length) return pos;
            int val = Integer.valueOf(list[pos]);
            if (val < lower || val > upper) return pos - 1;
            TreeNode cur = new TreeNode(val);
            if (isleft) par.left = cur;
            else par.right = cur;
            pos = deserializedfs(list, ++pos, cur, true, lower, val);
            pos = deserializedfs(list, ++pos, cur, false, val, upper);
            return pos;
        }

    }

}